package algorithm.List.Stack;

import java.util.Stack;

/**
 * 设计一个最小栈，即得到最小值的时间复杂度为O(1)
 * 设计思路是用两个基本栈，一个正常存放数据，另一个只存放当前的最小值
 */
public class MinStack {

    //这个最小栈主要实现取小和压入数据两个操作

    public static class MyMinStack{
        private Stack<Integer> data;
        private Stack<Integer> min;

        public MyMinStack() {
            data=new Stack<Integer>();
            min=new Stack<Integer>();
        }

        public void push(int val){
            data.push(val);
            if(min.isEmpty()||val<=min.peek()){
                min.push(val);
            }else{
                min.push(min.peek());
            }
        }
        public int getMin(){
            return min.peek();
        }
        public void pop(){
            data.pop();
            min.pop();
        }
    }

    public static class MyMinStackWithArray{
        private int[] data;
        private int[] min;
        private final int capacity=8001;
        private int size=0;

        public MyMinStackWithArray(){
            data=new int[capacity];
            min=new int[capacity];
        }
        public void push(int val){
            data[size]=val;
            if(size==0||val<min[size-1]){
                min[size]=val;
            }else{
                min[size]=min[size-1];
            }
            size++;
        }
        public void pop(){
            size--;
        }
        public int peek(){
            return data[size-1];
        }
        public int getMin(){
            return min[size-1];
        }
    }
}
